package zuochengyun.chapter5;

public class ThreeReverseAlgorithm {

	public static void main(String[] args) {
		ThreeReverseAlgorithm object = new ThreeReverseAlgorithm();
//		int[] nums = {-9  ,6 , 25,  68,  -63,  59 , 96};
		int[] nums = {4, 3, 6, 9, 41, 23, 68, 25, 68, 6, -9, 59, 96, -63};
		object.mergeSort(nums, 0, nums.length - 1);
		for(int i = 0; i < nums.length; i++){
			System.out.print(nums[i] + "  ");
		}
	}
	
	
	// 手摇算法也叫三次反转算法，我们可以通过一个简单例子引入该算法。若要将一个字符串abcdef变成defabc，
	// 简单的方法是用一个辅助数组来做，但是这种方式有O(n)的空间开销，因此在实际面试中，这种方法是不合格的。
	// 这时我们可以通过手摇算法轻松加愉快的解决这个问题，即首先反转abc将其变成cba（这可以通过设定两个指针指向首尾元素，
	// 然后通过交换指针指向的元素并将两指针往中间移动的方式来实现），同理def变成fed。此时字符串变为cbafed。
	// 再对其进行一次反转则达到了我们的要求defabc
	
	public void rotateWord(char[] chars, int size){
		if(chars == null || chars.length <= 0){
			return;
		}
		reverseString(chars, 0, size - 1);
		reverseString(chars, size, chars.length - 1);
		reverseString(chars, 0, chars.length - 1);
	}

	public void reverseString(char[] chars, int start, int end) {
		char temp = 0;
		while(start < end){
			temp = chars[start];
			chars[start] = chars[end];
			chars[end] = temp;
			start++;
			end--;
		}
	}
	
	//手摇算法通过原地的置换降低了空间复杂度
	//使用手摇算法将归并排序的空间复杂度降为O(1)
	//原地归并排序原理介绍，以下面的数组为例进行说明。
	//http://blog.csdn.net/acdreamers/article/details/24244643
	//10  30 50 60 80   20 25 55 65  73
	//两段都是排好序的，i和j分别指向10  和20
	//然后指针向后移动，直到找到比20大的值，即移动到30
	//此时我们知道i指针之前的值一定是两个有序数组中最小的
	//接下来我们移动j指针，直到我们找到比30大的，也就是55
	//10  30 50 60 80   20    25 55 65  73
	//    i    			index	  j
	//此时我们只需要翻转i到j这一段即可
	//是不是就跟上面翻转字符串的一样了呢
	//10  20 25 30   50 60 80  55 65 73
	//                i         j
	
	
	public void mergeSort(int[] nums, int left, int right){
		if(left < right){
			int middle = left + (right - left) / 2;
			//排序左端
			mergeSort(nums, left, middle);
			//排序右端
			mergeSort(nums, middle + 1, right);
			
			//此时两段都是有序的，合并这两段
			merge(nums, left, middle, right);
		}
	}
	
	//合并两段有序的数组
	public void merge(int[] nums, int left, int middle, int right){
		int i = left;
		int j = middle + 1;
		while(i < j && j <= right){
			//找到第一个比nums[j]大的
			while(i < j && nums[i] <= nums[j]){  
	            i++; 
			}
			//要暂存j的值，知道应该怎样翻转
			int index = j;
			
			while(j <= right && nums[j] < nums[i]){
				j++;
			}
			//进行翻转, 需要左移的是i ~ index - 1, index ~ j - 1
			convert(nums, i, index - 1, j - 1);
			
			//移动i
			i += j - index;
		}
	}
	
	//三次反转
	public void convert(int[] nums, int left, int index, int right) {
		reverse(nums, left, index);
		reverse(nums, index + 1, right);
		reverse(nums, left, right);
	}

	//反转
	private void reverse(int[] nums, int start, int end){
		int temp = 0;
		while(start < end){
			temp = nums[start];
			nums[start] = nums[end];
			nums[end] = temp;
			start++;
			end--;
		}
	}
}
